/*
 * @Author: szx
 * @Date: 2022-06-10 17:44:02
 * @LastEditTime: 2022-06-10 18:28:24
 * @Description:
 * @FilePath: \leetcode\面试题\16\19\19.js
 */
/**
 * @param {number[][]} land
 * @return {number[]}
 */
var pondSizes = function (land) {
    const dirs = [
            [-1, -1],
            [-1, 0],
            [-1, 1],
            [0, -1],
            [0, 0],
            [0, 1],
            [1, -1],
            [1, 0],
            [1, 1]
        ],
        m = land.length,
        n = land[0].length,
        used = new Array(m).fill(0).map(() => new Array(n).fill(false));

    const dfs = (r, c) => {
        if (land[r][c] != 0 || used[r][c]) return 0;
        used[r][c] = true;
        let res = 1;
        for (let [row, col] of dirs) {
            const x = row + r,
                y = col + c;
            if (x >= 0 && x < m && y >= 0 && y < n && !used[x][y]) res += dfs(x, y);
        }
        return res;
    };
    const res = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let tmp = dfs(i, j);
            if (tmp > 0) res.push(tmp);
        }
    }
    res.sort((a, b) => a - b);
    return res;
};
